///////////////////////////////////////////////////////////////////////////////
//
// Depth-First Search Maze Generator
//
// Original program written by Mike Gold, September 2005
// See Mike's page at:
// http://www.microgold.com
// Code available in MazeGenerator.ZIP from:
// http://www.gamespp.com/c/generatingMazes.html
// or from the C# Corner as dfsmaze.zip:
// http://www.c-sharpcorner.com/UploadFile/mgold/Maze09222005021857AM/Maze.aspx
//
// See also
// http://www.mazeworks.com/mazegen/mazetut/
// for an explanation of how mazes can be generated
//
// Modified by Trevor Taylor, Feb 2008
//
// Changes:
// Adjusted some of the initial parameters
// Created a separate menu item to set the maze parameters
// Renamed Form1 to MainForm
// Added a PictureBox for the Maze instead of drawing onto the Form
// (Required different handling for Paint and Resize events)
// Adjusted padding around the maze to be more even
// Added random Start and Finish cells (marked in green and red)
// (Which required a wall color parameter for drawing cells)
// Added Wall Thickness and allowed user to change it
// Added Save As menu option to save the bitmap
// Added Point-and-click to find out cell/pixel coords on the maze
// Created an icon using the generator itself
//
///////////////////////////////////////////////////////////////////////////////

using System;
using System.Collections;
using System.Drawing;

/*
 * create a CellStack (LIFO) to hold a list of cell locations  
set TotalCells = number of cells in grid  
choose a cell at random and call it CurrentCell  
set VisitedCells = 1  
   
while VisitedCells < TotalCells  
find all neighbors of CurrentCell with all walls intact   
if one or more found  
choose one at random  
knock down the wall between it and CurrentCell  
push CurrentCell location on the CellStack  
make the new cell CurrentCell  
add 1 to VisitedCells 
else  
pop the most recent cell entry off the CellStack  
make it CurrentCell 
endIf 
endWhile  
*/

namespace DFSAlgorithmMaze
{
	/// <summary>
	/// Summary description for Maze.
	/// </summary>
	public class Maze
	{
        // TT was 50
		public static int kDimension = 20;
        // TT - Add start and finish cells (always on left/right outside walls)
        public static int StartCell = 0;
        public static int FinishCell = kDimension-1;
        Cell[,] Cells = null;
		Stack CellStack = new Stack();
		int VisitedCells = 1;
		int TotalCells = kDimension * kDimension;
		Cell CurrentCell = null;

		public Maze()
		{
			Initialize();
		}

		private ArrayList GetNeighborsWithWalls(Cell aCell)
		{
			ArrayList Neighbors = new ArrayList();
            // TT - Was not used
			//int count = 0;
			for (int countRow = -1; countRow <= 1; countRow++)
				for (int countCol = -1; countCol <= 1; countCol++)
				{
					if ( (aCell.Row + countRow < kDimension) &&  
						 (aCell.Column+countCol < kDimension) &&
						 (aCell.Row+countRow >= 0) &&
						 (aCell.Column+countCol >= 0) &&
						 ((countCol == 0) || (countRow == 0)) &&
						 (countRow != countCol)
						)
					{
						if (Cells[aCell.Row+countRow, aCell.Column+countCol].HasAllWalls())
						{
							Neighbors.Add( Cells[aCell.Row+countRow, aCell.Column+countCol]);
						}
					}
				}

			return Neighbors;
		}

		public void Initialize()
		{
			Cells = new Cell[kDimension, kDimension];
			TotalCells = kDimension * kDimension;
			for (int i = 0; i < kDimension; i++)
				for (int j = 0; j < kDimension; j++)
				{
					Cells[i,j] =  new Cell();
					Cells[i, j].Row = i;
					Cells[i, j].Column = j;
				}

            // TT - Add start and finish cells
			//CurrentCell = Cells[0,0];
            StartCell = Cell.TheRandom.Next(0, kDimension);
            FinishCell = Cell.TheRandom.Next(0, kDimension);
            CurrentCell = Cells[0, StartCell];
            VisitedCells = 1;
			CellStack.Clear();
		}

		public void  Generate()
		{
			while (VisitedCells < TotalCells)
			{
				// get a list of the neighboring cells with all walls intact
				ArrayList AdjacentCells = GetNeighborsWithWalls(CurrentCell);
				// test if a cell like this exists
				if (AdjacentCells.Count > 0)
				{
					// yes, choose one of them, and knock down the wall between it and the current cell
					int randomCell = Cell.TheRandom.Next(0, AdjacentCells.Count);
					Cell theCell = ((Cell)AdjacentCells[randomCell]);
					CurrentCell.KnockDownWall(theCell);
					CellStack.Push(CurrentCell); // push the current cell onto the stack
					CurrentCell = theCell; // make the random neighbor the new current cell
					VisitedCells++;
				}
				else
				{
					// No cells with walls intact, pop current cell from stack
					CurrentCell = (Cell)CellStack.Pop();
				}

			}
		}


		public void Draw(Graphics g)
		{
			for (int i = 0; i < kDimension; i++)
				for (int j = 0; j < kDimension; j++)
				{
                    // TT - Add wall color
					Cells[i,j].Draw(g, Color.Blue);
				}

            // TT - Show start and finish cells
            Cells[0, StartCell].Draw(g, Color.Green);
            Cells[kDimension-1, FinishCell].Draw(g, Color.Red);
        }
	}
}
